package me.mingshan.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.cn/problems/missing-number/
 * <p>
 * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [3,0,1]
 * <p>
 * 输出：2
 * <p>
 * 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [0,1]
 * <p>
 * 输出：2
 * <p>
 * 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
 * <p>
 * 示例 3：
 * <p>
 * 输入：nums = [9,6,4,2,3,5,7,0,1]
 * <p>
 * 输出：8
 * <p>
 * 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
 *
 * @author hanjuntao
 * @date 2025/6/4 0004
 */
public class L_268_missing_number {

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        //System.out.println(missingNumber4(nums));

        int[] nums2 = {0, 1};
        //System.out.println(missingNumber4(nums2));

        int[] nums3 = {3, 0, 1};
        System.out.println(missingNumber4(nums3));

        int[] nums4 = {3, 2, 0};
        //System.out.println(missingNumber4(nums4));

        System.out.println(2 ^ 0);
        System.out.println(2 ^ 4);
    }

    /**
     * 使用map
     *
     * @param nums
     * @return
     */
    public static int missingNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            map.put(num, num);
        }

        int n = nums.length;
        for (int i = 0; i <= n; i++) {
            if (!map.containsKey(i)) {
                return i;
            }
        }

        return -1;
    }

    /**
     * 遍历数组
     *
     * @param nums
     * @return
     */
    public static int missingNumber2(int[] nums) {
        int n = nums.length;

        for (int i = 0; i <= n; i++) {
            boolean exist = false;
            for (int j = 0; j < n; j++) {
                if (nums[j] == i) {
                    exist = true;
                    break;
                }
            }

            if (!exist) {
                return i;
            }
        }

        return -1;
    }

    /**
     * 排序，然后根据下表判断缺失的数字
     * <p>
     * 注意：
     * 数组的长度为 n ，但是数组的元素少一个，
     *
     * @param nums
     * @return
     */
    public static int missingNumber3(int[] nums) {
        Arrays.sort(nums);

        for (int i = 0; i <= nums.length; i++) {
            // 处理边界情况
            if (i == nums.length) {
                return i;
            } else {
                if (nums[i] != i) {
                    return i;
                }
            }
        }

        return -1;
    }

    /**
     * 原地交换位置：
     * <p>
     * 将nums[i] = x的值，放到nums[x]的位置上，
     * nums[x]原来的值，放到nums[i]上。
     * 注意交换后i的位置可能不满足上面的条件，如果继续向后走，可能把这个位置的数据漏处理了，需要再次检查，
     * <p>
     * 然后遍历数组，如果nums[i] != i，则返回i。
     * <p>
     * 如果都没有，就是最后一个元素不在数组中
     *
     * @param nums
     * @return
     */
    public static int missingNumber4(int[] nums) {
        int n = nums.length;
        // 交换位置
        for (int i = 0; i < n; i++) {
            int x = nums[i];

            // x的值小于数组长度，并且x的值不等于i
            if (x < n && x != i) {
                swap(nums, x, i);
                // i--是为了在交换后再次检查当前位置（因为交换后，当前位置i的新元素可能还不满足条件）
                // 如果不再次检查，则会漏掉i这个位置的元素，出现逻辑错误
                i--;
            }
        }

        // 遍历数组，如果nums[i] != i，则返回i
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i) {
                return i;
            }
        }

        // 都没有，就是最后一个元素不在数组中
        return nums.length;
    }

    /**
     * 交换a,b两个位置的元素
     *
     * @param a 位置a
     * @param b 位置b
     */
    public static void swap(int[] source, int a, int b) {
        int temp = source[a];
        source[a] = source[b];
        source[b] = temp;
    }

    /**
     * 异或求缺失的数字
     * <p>
     * 核心思想：利用异或的以下性质
     * <p>
     * a ^ a = 0（相同数异或结果为0）
     * <p>
     * a ^ 0 = a（任何数与0异或不变）
     * <p>
     * 异或满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b
     * <p>
     * 操作步骤：
     * <p>
     * 假设完整数字范围是 [0, n]（共 n+1 个数）
     * <p>
     * 对 所有下标 [0, n-1] 和 所有数字 [0, n] 进行异或：
     * <p>
     * result = (0^1^2^...^n) ^ (nums[0]^nums[1]^...^nums[n-1])
     * 由于除缺失数字外，其他数字在两边的异或操作中各出现一次，最终会相互抵消
     * <p>
     * 最终结果就是缺失的数字
     *
     * @param nums
     * @return
     */
    public static int missingNumber5(int[] nums) {
        int n = nums.length;
        // 初始化为n（因为下标范围是0到n-1，n需要额外处理）
        int missing = n;

        for (int i = 0; i < n; i++) {
            missing ^= i;       // 异或所有下标 (0 到 n-1)
            missing ^= nums[i]; // 异或数组中的所有元素
        }
        return missing;
    }

}
